package sort.bublesort;

import sort.generator.ArrayGenerator;
import sort.helper.SortingHelper;

import java.util.Arrays;

/**
 * @author XY
 * @version 1.0
 * @date 2021/12/9 16:44
 * @Description 冒泡排序
 */
public class BubbleSort {


    //冒泡排序O(n)
    public static <E extends Comparable<E>> void sort(E[] arr){
        for(int i =0 ;i<arr.length-1;i++){
            for(int j = 0 ;j<arr.length-i-1; j++){
                if(arr[j+1].compareTo(arr[j])<0){
                    E temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    //冒泡排序的优化,有序情况下O(n)
    public static <E extends Comparable<E>> void sort2(E[] arr){
        for(int i =0 ;i<arr.length-1;i++){
            boolean flag = false;
            for(int j = 0 ;j<arr.length-i-1; j++){
                if(arr[j+1].compareTo(arr[j])<0){
                    E temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = true;
                }
            }
            //如果已经是有序的，就直接退出循环
            if(!flag){
                break;
            }
        }
    }

    //冒泡排序的优化,在出现一次排序后，不止一个元素被排好了序，那么下次排序即可排除掉排了序的那几个 （2,1,3,8,4,5,6,7）
    public static <E extends Comparable<E>> void sort3(E[] arr){
        for(int i =0 ;i<arr.length-1; ){
            int index = 0;
            for(int j = 0 ;j<arr.length-i-1; j++){
                if(arr[j+1].compareTo(arr[j])<0){
                    E temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    index = j+1;
                }
            }
            i = arr.length-index;
        }
    }


    public static void main(String[] args) {
        int n = 100000;
        Integer[] integers = ArrayGenerator.generateRandomArray(n, n);
        Integer[] integers2 = Arrays.copyOf(integers, n);

        Integer[] integers1 = search.generator.ArrayGenerator.generateOrderedArray(n);
        Integer[] integers3 = Arrays.copyOf(integers1, n);

        SortingHelper.sortTest("BubbleSort",integers);
        SortingHelper.sortTest("BubbleSort2",integers2);
        System.out.println("============");
        SortingHelper.sortTest("BubbleSort",integers1);
        SortingHelper.sortTest("BubbleSort2",integers3);

    }
}
